package leetcode_day._2021._202103;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 92. 反转链表 II
 * 反转链表
 * 反转 left 到 right 之间的数字
 * 2020/3/18
 * 算法：链表
 *   使用栈来存放 left 到 right 之间的数字
 *   当 right <= flag <= right 时，把数字存放到栈中
 *   还要记录第 left 的节点，第二次遍历看栈是否为空，从第 left 节点开始
 */
public class _18_92 {
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        Deque<Integer> stack = new ArrayDeque<>();
        ListNode tem = head, Left = head;
        int flag = 0;
        while (tem != null) {
            ++flag;
            if (flag == left) {
                Left = tem;
            }
            if (flag >= left && flag <= right) {
                stack.push(tem.val);
            }
            if (flag == right) {
                break;
            }
            tem = tem.next;
        }
        while (!stack.isEmpty()) {
            Left.val = stack.pop();
            Left = Left.next;
        }
        return head;
    }

    /**
     * 定义一个伪指针, 因为可能会出现反转第一个个元素
     * 定义 p0 指向第 left 的前一个元素
     * 当 left 到 right 之间的元素反转完成后, pre 指向第 right 个元素, right 指向第 right + 1 个元素
     * p0.next 指向第 left 个元素
     */
    public ListNode reverseBetweenLinked(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1, head), p0 = dummy;
        for (int i = 0; i < left - 1; i++) p0 = p0.next;
        ListNode pre = null, cur = p0.next, next = null;
        for (int i = 0; i < right - left + 1; i++) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        p0.next.next = cur;
        p0.next = pre;
        return dummy.next;
    }
}
